%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require Positive integers $n$ and $N$ such that $1 \leq N \leq \binom{n}{2}$.
\Ensure A random graph from $G(n,N)$.
%%
%% algorithm body
\State $\MyMax \gets \binom{n}{2}$
\If{\rm $n = 1$ or $N = \MyMax$}
  \State \Return $K_n$
\EndIf
\State $G \gets \overline{K_n}$
\State $u \gets 0$
\State $v \gets 1$
\State $t \gets 0$\Comment{number of candidates processed so far}
\State $k \gets 0$\Comment{number of edges selected so far}
\While{$\MyTrue$}
  \State $r \gets$ draw uniformly at random from $\{0, 1, \dots, \MyMax - t\}$
  \If{$r < N - k$}
    \State add edge $uv$ to $G$
    \State $k \gets k + 1$
    \If{$k = N$}
      \State \Return $G$
    \EndIf
  \EndIf
  \State $t \gets t + 1$
  \State $v \gets v + 1$
  \If{$v = n$}
    \State $u \gets u + 1$
    \State $v \gets u + 1$
  \EndIf
\EndWhile
\end{algorithmic}
